package com.banmao.algorithm.No201To300.No297;

import com.banmao.algorithm.utils.vo.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.LinkedList;

/**
 *  效率很低
 */
public class Solution {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return null;
        }

        // 层序遍历
        ArrayDeque<Object> deque = new ArrayDeque<>();
        deque.push(root);

        ArrayList<String> resultStr = new ArrayList<>();

        while (!deque.isEmpty()) {
            int size = deque.size();

            for (int i = 0; i < size; i++) {
                Object pop = deque.pop();

                if (pop instanceof String) {
                    resultStr.add("null");
                } else {
                    TreeNode pop_r = (TreeNode) pop;
                    resultStr.add(String.valueOf(pop_r.val));
                    if(pop_r.left != null) {
                        deque.add(pop_r.left);
                    } else {
                        deque.add("null");
                    }

                    if(pop_r.right != null) {
                        deque.add(pop_r.right);
                    } else {
                        deque.add("null");
                    }
                }

            }

        }
        return resultStr.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {

        if (data == null) {
            return null;
        }
        data = data.substring(1, data.length() - 1).replace(" ", "");
        String[] array = data.split(",");

        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        TreeNode root = new TreeNode(Integer.parseInt(array[0]));
        queue.add(root);

        // 题目中一般提供的示例是层序遍历
        int index = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.pollFirst();
                if(index >= array.length) {
                    break;
                }
                if (poll != null) {
                    String leftValue = array[index++];
                    String rightValue = array[index++];
                    poll.left = "null".equalsIgnoreCase(leftValue) ? null : new TreeNode(Integer.parseInt(leftValue));
                    queue.add(poll.left);
                    poll.right = "null".equalsIgnoreCase(rightValue) ? null : new TreeNode(Integer.parseInt(rightValue));
                    queue.add(poll.right);
                }
            }
        }

        return root;
    }

}
